Field of the Invention
The present invention relates generally to data pattern analysis. More particularly, this invention relates to data pattern analysis using deterministic finite automaton.
Description of the Related Art
Deterministic finite automaton (DFA) or deterministic finite state machine is a set of states tied together by a set of transitions, where transitions specify movement from one state to another based on some input. Thus, a deterministic finite automaton at a given state and for a given input has only one transition to a next state. Examples of such deterministic finite automaton may be designed in hardware or software to produce results based on the state and any input. Some applications for deterministic finite automaton are used in electronic systems, such as network equipment and computer operated systems, to control and run processes.
To increase the speed at which a deterministic finite automaton operates on an electronic system current systems load an array into memory for each state of the deterministic finite automaton. Each array contains information on the current state and defines what the next state will be given a certain input. As the number of states and transitions between states of a deterministic finite automaton increases the size of the array also increases. This creates the need for large amounts of memory necessary to store the information needed to execute a deterministic finite automaton. As the memory demands increase so does the cost of implementing a deterministic finite automaton.